<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <body>
    <script>
      /* 
      思路：这题其实没那么可怕，和二叉搜索树查找val值一样。
      利用二叉搜索树的性质，找到空值时，根据记录的父节点的值，进行判断插入
      */
      var insertIntoBST = function (root, val) {
        if (!root) return new TreeNode(val)
        let parentNode = new TreeNode(0)
        function preOrder(root) {
          //这也就是为什么 先序遍历 节点不存在需要return
          if (root == null) {
            //找到了空位
            let node = new TreeNode(val)
            if (parentNode.val < node.val) {
              parentNode.right = node
            } else {
              parentNode.left = node
            }
            return
          }
          //注意啊，这个parentNode必须写在if(root==null)后面，不然没法记录了...
          //其次，插入完成后，必须直接return掉，不然null.val会报错
          parentNode = root

          if (root.val < val) {
            preOrder(root.right)
          }
          if (root.val > val) {
            preOrder(root.left)
          }
        }
        preOrder(root)
        return root
      }
    </script>
  </body>
</html>
